class Solution {
public:
    int search(vector<int>& nums, int target) {

        //方法1 直接去遍历
        // for (int i = 0 ;i < nums.size();i++)
        // {
        //     if (nums[i] == target)
        //     {

        //         return i;
        //     }
        // }

        //方法2 二分的方法 写个递归函数
        if (nums.size() == 0)
        {
            return -1;
        }
        else if(nums.size() == 1)
        {
            if (nums[0] == target)
            {
                return 0;
            }
            else
            {
                return -1;
            }
        }
        else
        {
            // 1 2 3    //1 2 3 4
            int mid = (nums.size()) / 2;
            int left = 0;
            int right = nums.size();
            while (left < right)
            {
                if (nums[mid] == target)
                {
                    return mid;

                }
                else if(nums[mid] > target)
                {


                    if ((right - left) == 1)
                    {
                        if(nums[(right - left) / 2] == target)
                        {
                            return (right - left) / 2;
                        }
                        else
                        {
                                return -1;
                        }
                    }
                    else
                    {
                        right = mid;
                        mid = (left + right)/2;
                    }
                    
                }
                else
                {
                    if ((right - left) == 1)
                    {
                        if(nums[(right - left) / 2] == target)
                        {
                            return (right - left) / 2;
                        }
                        else
                        {
                                return -1;
                        }
                    }
                    else
                    {
                        left = mid;
                        mid = (left + right) /2;
                    }

                }
            }
            return -1;
        }
        return -1;


    }
};


// 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。


// 示例 1:

// 输入: nums = [-1,0,3,5,9,12], target = 9
// 输出: 4
// 解释: 9 出现在 nums 中并且下标为 4
// 示例 2:

// 输入: nums = [-1,0,3,5,9,12], target = 2
// 输出: -1
// 解释: 2 不存在 nums 中因此返回 -1

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/binary-search
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。